home *** CD-ROM | disk | FTP | other *** search
/ Mission 3 / Mission 3.zip / Mission 3.iso / demovers / scripter / libs / sort.lib < prev   
Text File  |  1998-09-26  |  1KB  |  74 lines
  1. proc qsort(&arr, start, end, compare(&elem1, &elem2))
  2. local up, down, pivot;
  3. {
  4.     while (end > start) {
  5.     up = start;
  6.     down = end;
  7.     pivot = arr[(start + end) / 2];
  8.  
  9.     do {
  10.         while (compare(arr[up], pivot) < 0) ++up;
  11.         while (compare(arr[down], pivot) > 0) --down;
  12.         if (up <= down) swap(arr[up++], arr[down--]);
  13.     } while (up <= down);
  14.  
  15.     if (down - start > end - up) {
  16.         if (end > up) qsort(arr, up, end, compare);
  17.         end = down;
  18.     }
  19.     else {
  20.         if (down > start) qsort(arr, start, down, compare);
  21.         start = up;
  22.     }
  23.     }
  24. }
  25.  
  26.  
  27. proc qsort_array(&arr, compare(&elem1, &elem2))
  28. {
  29.     qsort(arr, 0, arr.length - 1, compare);
  30. }
  31.  
  32.  
  33. proc lfind(&key, &array, max, compare(&elem1, &elem2))
  34. local i;
  35. {
  36.     if (max > array.length) max = array.length;
  37.  
  38.     for (i = 0; i < max; ++i)
  39.         if(compare(array[i], key) == 0) return i;
  40.  
  41.     return -1;
  42. }
  43.  
  44.  
  45. proc lsearch(&key, &array, &max, compare(&elem1, &elem2))
  46. local idx;
  47. {
  48.     if ((idx = lfind(key, array, max, compare)) < 0) {
  49.         if (array.length <= max) array.length = max + 1;
  50.         array[max++] = key;
  51.         return max - 1;
  52.     }
  53.  
  54.     return idx;
  55. }
  56.  
  57.  
  58. proc bsearch(&key, &array, max, compare(&elem1, &elem2))
  59. local min, idx, cval;
  60. {
  61.     if (max > array.length) max = array.length;
  62.     --max;
  63.     min = 0;
  64.  
  65.     while (min <= max) {
  66.         idx = (min + max) / 2;
  67.         if ((cval = compare(array[idx], key)) == 0) return idx;
  68.         if (cval > 0) max = idx - 1;
  69.         else          min = idx + 1;
  70.     }
  71.  
  72.     return -1;
  73. }
  74.